package 动态规划.棋盘dp;

import org.junit.Test;


/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/13 10:59
 */
public class lc931下降最小路径和 {

    /*
     注意一下灵神的题单
     */

    // 这个题 ，也从侧面说明了一点， 你对 棋盘 dp 并不是很熟悉！
    public int recursion(int i, int j, int martix[][], Integer[][] dp) {
        if (j < 0 || j == martix[0].length) {
            return Integer.MAX_VALUE;
        }
        if (dp[i][j] != null) {
            return dp[i][j];
        }
        // 如果 i == len - 1 ，走到最后直接返回就行
        if (i == martix.length - 1) {
            return martix[i][j];
        }
        return dp[i][j] = Math.min(recursion(i + 1, j + 1, martix, dp), Math.min(recursion(i + 1, j - 1, martix, dp), recursion(i + 1, j, martix, dp))) + martix[i][j];
    }


    public int solve(int martix[][]) {
        int ans = Integer.MAX_VALUE;
        Integer dp[][] = new Integer[martix.length][martix[0].length];
        for (int j = 0; j < martix[0].length; j++) {
//            ans = Math.min(recursion(0, j, martix, dp), ans);
            ans = Math.min(dfs(0, j, martix, dp), ans);
        }
        return ans;
    }


    /*
     Error 版本

     j 越界 和 i 越界 的处理方式不一样的 ！
     再次 思考这个问题的时候， 去想一下这个点 ：

     如果 i 越界 只有 i + 1 这种情况， 也就是走到了 最后， 直接返回 0
     或者直接 在 i == martix.length - 1 的时候 直接返回 当前 数组值就行

    而 j 越界 这里面 是 从 **侧边越界 **   而侧边越界的话， 是没有走到最后， 拿着就是一个不符合条件 结果， 这里返回一个对结果没影响的值 MAX

     */
    public int recursion(int i, int j, int martix[][]) {
        if (i == martix.length || j < 0 || j == martix[0].length) {
            return 0;
        }
        int ans1 = recursion(i + 1, j + 1, martix);
        int ans2 = recursion(i + 1, j - 1, martix);
        int ans3 = recursion(i + 1, j, martix);

        return Math.min(ans1, Math.min(ans2, ans3));
    }


    @Test
    public void test() {
//        int matrix[][] = {{-19, 57}, {-40, -5},{}};
        int matrix[][] = {{2, 1, 3}, {6, 5, 4}, {7, 8, 9}};
        System.out.println(solve(matrix));
    }


    // 2023/8/10

    // 只需要关心两侧， 也就是 j 的边界情况就行了！
    public int dfs(int i, int j, int matrix[][], Integer dp[][]) {
        if (j < 0 || j >= matrix[0].length) {
            return Integer.MAX_VALUE / 2;
        }
        if (i == matrix.length - 1) {
            return matrix[i][j];
        }
        if (dp[i][j] != null) {
            return dp[i][j];
        }
//        int ans = 0;
        return dp[i][j] = Math.min(dfs(i + 1, j - 1, matrix, dp), Math.min(dfs(i + 1, j, matrix, dp), dfs(i + 1, j + 1, matrix, dp))) + matrix[i][j];
    }


}
